package HighMethod08;

/**
 * 矩阵连乘
 * 1、矩阵的乘法运算
 * 2、矩阵连乘的舒顺序使得乘法运算次数最小
 * 3、打印矩阵乘法顺序的矩阵
 */
public class MartrixMultiply {

    //计算两个矩阵相乘产生的新矩阵
    public static void MartrixMul(int[][] a, int[][] b, int[][] c, int ra, int ca, int rb, int cb) {
        if (ca != rb) {                 //如果第一个矩阵的列数不等于第二个矩阵的行数直接返回
            System.out.println("第一个矩阵的列数不等于第二个矩阵的行数，不满足矩阵相乘的条件！");
            return;
        }

        for (int i = 0; i < ra; i++) {      //新矩阵的行
            for (int j = 0; j < cb; j++) {  //新矩阵的列
                int tmpSum = 0;
                for (int k = 0; k < ca; k++) {      //计算第一个矩阵的列元素与第二个矩阵的行元素乘积之和
                    tmpSum += a[i][k] * b[k][j];
                }
                c[i][j] = tmpSum;           //更新新矩阵的元素
            }
        }   //矩阵相乘的乘法运算次数为i*j*k
    }

    //非递归方法，求接矩阵连乘最小乘法运算次数（窗口方案,这里的窗口一直在变，TCP/IP协议的窗口大小不变）
    public static int NiceMatrixChain(int[] p, int[][] m) {
        int len = p.length - 1;
        for (int i = 0; i <= len; i++) {
            m[i][i] = 0;
        }
        for (int r = 2; r <= len; r++) {
            for (int i = 1; i <=len-r+1; i++) {      //
                int j =i+r-1;           //i基准
                m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];   //
                for (int k = i + 1; k < j; k++) {           //求最小值
                    int t = m[i][k] + m[k + 1][j] + p[i-1] * p[k] * p[j];       //
                    m[i][j] = Math.min(m[i][j],t);
                }
                Print_Ar(m);
                System.out.println("----------------------------------");
            }
        }
        return m[1][len];
    }

    //递归方法，求矩阵连乘最小乘法运算次数（存在重复计算，不推荐）
    public static int MatruxChain(int[] p, int i, int j) {
        if (i == j) {
            return 0;
        } else {
            int minnum = MatruxChain(p, i, i) + MatruxChain(p, i + 1, j) + p[i - 1] * p[i] * p[j];
            for (int k = i + 1; k < j; k++) {
                int t = MatruxChain(p, i, k) + MatruxChain(p, k + 1, j) + p[i - 1] * p[k] * p[j];
                if (minnum > t) {
                    minnum = t;
                }
            }
            return minnum;
        }
    }

    public static void main(String[] args) {
        /*int[][] a = {
                {1, 2, 3},
                {1, 2, 3},
        };
        int[][] b = {
                {1, 1},
                {1, 1},
                {1, 1}
        };
        int[][] c = new int[a.length][b[0].length];
        MartrixMul(a, b, c, a.length, a[0].length, b.length, b[0].length);
        for (int i = 0; i < c.length; i++)
        System.out.println(Arrays.toString(c[i]));      /两个矩阵乘积的结果
*/

//        int []p = {30,30,35,35,15,15,5,5,10,10,20,20,25};
        int[] p = {30, 35, 15, 5, 10, 20, 25};      //最少15125次乘法运算
        int len = p.length;
        int[][] m = new int[p.length][p.length];        //查表用到的矩阵，避免重复计算
        int[][] s = new int[p.length][p.length];        //记录划分点
//        System.out.println("最少连乘次数：" + MatruxChain(p, 1, len - 1));
//        System.out.println("最少连乘次数：" + MatruxChainOptimized(p, 1, len - 1, m, s));
//        Print_Ar(m);        //打印计算的存储矩阵
//        System.out.println();
//        Print_Ar(s);        //打印划分点矩阵
//        TraceBack(s, 1, len - 1);   //  打印矩阵连乘的运算次序

        //非递归，滑动窗口求最少连乘次数
        System.out.println("最少连乘次数：" + NiceMatrixChain(p, m));
    }


    //递归方法，求矩阵连乘最小乘法运算次数（查表方法计算（不存在重复计算），推荐！）
    private static int MatruxChainOptimized(int[] p, int i, int j, int[][] m, int[][] s) {
        if (i == j) {
            return 0;
        } else if (m[i][j] > 0) {
            return m[i][j];
        } else {
            m[i][j] = MatruxChainOptimized(p, i + 1, j, m, s) + p[i - 1] * p[i] * p[j];
            s[i][j] = i;    //记录划分点的矩阵
            for (int k = i + 1; k < j; k++) {
                int t = MatruxChainOptimized(p, i, k, m, s) + MatruxChainOptimized(p, k + 1, j, m, s) + p[i - 1] * p[k] * p[j];
                if (m[i][j] > t) {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
            return m[i][j];
        }
    }

    public static void TraceBack(int[][] s, int i, int j) {
        if (i < j) {
            TraceBack(s, i, s[i][j]);
            TraceBack(s, s[i][j] + 1, j);
            System.out.println("Multiply A " + i + ',' + s[i][j] + " and A " + (s[i][j] + 1) + ',' + j);
            //思考：如何根据划分点矩阵打印计算矩阵乘积
            //思路：判断i与s[i][j]不相等计算乘积既调用函数MartrixMul()，判断i与s[i][j]不相等计算乘积既调用函数MartrixMul()
            //      最后还要计算乘积既调用函数MartrixMul()；
            // 难的的是测试用例多
        }
    }


    //打印矩阵函数
    public static void Print_Ar(int[][] m) {

        for (int[] ints : m) {
            for (int anInt : ints) {
                System.out.printf("%7d", anInt);
            }
            System.out.println();
        }
    }


}
